In this paper, we propose a new digital signature scheme based on a third order linear feedback shift register for signing documents. This signature scheme is different from most of the signature schemes that are based on discrete logarithm problem, elliptic curves discrete logarithm problem, RSA or quadratic residues. An efficient algorithm for computing kth term of a sequence is also presented. The advantage of this scheme is that the computation is efficient than Schnorr scheme. We also show that the security of the proposed signature scheme is equivalent to that of Schnorr signature scheme.

This paper proposes a heuristic algorithm which, given a basis of a subspace of the space of cuspforms of weight 2 for 0(N) which is invariant for the action of the Hecke operators, tests whether the subspace corresponds to a quotient A of the jacobian of the modular curve X0(N) such that A is the jacobian of a curve C. Moreover, equations for such a curve C are computed which make the quotient suitable for applications in cryptography. One advantage of using such quotients of modular jacobians is that fast methods are known for finding their number of points over finite fields.

In recent years, the study of the security of Elliptic Curve Cryptosystems (ECCs) have been received much attention. The MOV algorithm, which reduces the elliptic curve discrete log problem (ECDLP) to the discrete log problem in finite fields with the Weil pairing, is a representative attack on ECCs. Recently Kanayama et al. observed a realization of the MOV algorithm for non-supersingular elliptic curves under the weakest condition. Shikata et al. independently considered a realization of the MOV algorithm for non-supersingular elliptic curves and proposed a generalization of the MOV algorithm. This short note explicitly shows that, under a usual cryptographical condition, we can apply the MOV algorithm to non-supersingular elliptic curves by using the multiplication by constant maps as in the case of supersingular. Namely, it is explicitly showed that we don't need such a generalization in order to realize the MOV algorithm for non-supersingular elliptic curves under a usual cryptographical condition.

In this paper, first, we propose two of the high rate methods based on Morii-Kasahara cryptosystem. Method A-I is based on Schalkwijk algorithm. Method A-II is based on the extended Schalkwijk algorithm, which is proposed in this paper. We then show that these proposed methods can yield a higher rate compared with ElGamal cryptosystem. Next, we also propose two methods for a fast encryption by dividing the message vector into several pieces. Regarding each of the divided vectors as an index, we can realize a fast transformation of the index into a limited weight vector. In Method B-I, Schalkwijk algorithm is used for the fast transformation. In Method B-II, the fast transformation is realized with the method of table-lookup. These methods can realize a faster encryption than Method A-I, Method A-II and Morii-Kasahara cryptosystem. The security of these proposed methods are based on the security of Morii-Kasahara cryptosystem.

Gaudry has described a new algorithm (Gaudry's variant) for the discrete logarithm problem (DLP) in hyperelliptic curves. For a hyperelliptic curve of a small genus on a finite field GF(q), Gaudry's variant solves for the DLP in time O(q2+ε). This paper shows that Cab curves can be attacked with a modified form of Gaudry's variant and presents the timing results of such attack. However, Gaudry's variant cannot be effective in all of the Cab curve cryptosystems. This paper also provides an example of a Cab curve that is unassailable by Gaudry's variant.

We study how to generalize a key agreement and password authentication protocol on the basis of the well known hard problems such as a discrete logarithm problem and a Diffie-Hellman problem. The key agreement and password authentication protocol is necessary for networked or internetworked environments to provide the user knowledge-based authentication and to establish a new cryptographic key for the further secure session. The generalized protocol implies in this paper to require only weak constraints and to be generalized easily in any other cyclic groups which preserve two hard problems. The low entropy of password has made it difficult to design such a protocol and to prove its security soundness. In this paper, we devise a protocol which is easy to be generalized and show its security soundness in the random oracle model. The proposed protocol reduces the constraints extremely only to avoiding a smooth prime modulus. Our main contribution is in solving the password's low entropy problem in the multiplicative group for the generalization.

In this paper, we propose an idea of the generalization of threshold signature and authenticated encryption for group communications. The concept of the (t, n) threshold signature with (k, l) shared verification is implemented in group-oriented cryptosystems. In the system, any t members can represent a group to sign a message and any k verifiers can represent another group to authenticate the signature. By integrating the cryptographic techniques of data encryption, digital signature and message recovery, a group-oriented authenticated encryption scheme with (k, l) shared verification is also proposed. The message expansion and communication cost can also be reduced in our schemes.

The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field Fq is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q-1, such a minimum extension degree is the minimum k such that l|qk-1, which is equivalent to the condition under which the Frey-Ruck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an l-torsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.

We propose an untraceable electronic money system. Our system uses the partially blind signature based on the discrete logarithm problem, and applies secret key certificates to the payment protocol.

Super-anomalous elliptic curves over a ring Z/nZ ;(n=Πi=1k piei) are defined by extending anomalous elliptic curves over a prime filed Fp. They have n points over a ring Z/nZ and pi points over Fpi for all pi. We generalize Satoh-Araki-Smart algorithm and Ruck algorithm, which solve a discrete logarithm problem over anomalous elliptic curves. We prove that a "discrete logarithm problem over super-anomalous elliptic curves" can be solved in deterministic polynomial time without knowing prime factors of n.

The MOV and FR algorithms, which are representative attacks on elliptic curve cryptosystems, reduce the elliptic curve discrete logarithm problem (ECDLP) to the discrete logarithm problem in a finite field. This paper studies these algorithms and introduces the following three results. First, we show an explicit condition under which the MOV algorithm can be applied to non-supersingular elliptic curves. Next, by comparing the effectiveness of the MOV algorithm to that of the FR algorithm, it is explicitly shown that the condition needed for the MOV algorithm to be subexponential is the same as that for the FR algorithm except for elliptic curves of trace two. Finally, a new explicit reduction algorithm is proposed for the ECDLP over elliptic curves of trace two. This algorithm differs from a simple realization of the FR algorithm. Furthermore, we show, by experimental results, that the running time of the proposed algorithm is shorter than that of the original FR algorithm.

In Adleman's Function Field Sieve algorithm solving the discrete logarithm problem in a finite field, it is assumed that a random bivariate polynomial in the certain class is absolutely irreducible with high probability. In this letter we point out that if we use Cab type random polynomials then we always get absolutely irreducible polynomials. We can also simplify the calculation of a product of many rational functions on a curve that belongs to the field of definition by the use of a Cab curve.

In this paper, we propose a new conference key distribution scheme and the supervision of a conference when users are in a level-based hierarchy. In a conference key distribution system, one message is transmitted to the participants from a chairman, a legitimate member can decrypt it and reveal the common session key. The proposed scheme can be implemented without using any tamper-proof hardware. For users in a level-based hierarchy, by applying the key distribution scheme, the higher priority users can derive the conference key and supervise the lower level users' communications. Further, the users in the same level who are not members of the conference or in lower levels can not expose the conference key. To break the common session key, a malicious user has to suffer from the difficulty of factorization and discrete logarithm problems.

Secret sharing schemes are good for protecting the important secrets. They are, however, inefficient if the secret shadow held by the shadowholder cannot be reused after recovering the shared secret. Traditionally, the (t, n) secret sharing scheme can be used only once, where t is the threshold value and n is the number of participants. To improve the efficiency, we propose an efficient dynamic secret sharing scheme. In the new scheme, each shadowholder holds a secret key and the corresponding public key. The secret shadow is constructed from the secret key in our scheme, while in previously proposed secret sharing schemes the secret key is the shadow. In addition, the shadow is not constructed by the shadowholder unless it is necessary, and no secure delivery channel is needed. Morever, this paper will further discuss how to change the shared secret, the threshold policy and cheater detection. Therefore, this scheme provides an efficient way to maintain important secrets.

Nyberg and Rueppel recently proposed a new EIGamal-type digital signature scheme with message recovery feature and its six variants. The advantage of small signed message length is effective especially in some applications like public key certifying protocols or the key exchange. But two forgeries that present a real threat over such applications are pointed out. In certifying public keys or key exchanges, redundancy is not preferable in order to store or transfer small data. Therefore the current systems should be modified in order to integrate the Nyberg-Ruepple's signature into such applications. However, there has not been such a research that prevents the forgeries directly by improving the signature scheme. In this paper, we investigate a condition to avoid the forgeries directly. We also show some new message recovery signatures strong against the forgeries by adding a negligible computation amount to their signatures, while not increasing the signature size. The new scheme can be integrated into the above application without modifying the current systems, while maintaining the security.

To improve the efficiency for the threshold schemes, the major problem is that the secret shadows cannot be reused after renewing or recovering the shared secret. However, if the secret shadows cannot be reused, the established threshold scheme is limited to be used only once. It is inefficient to reconstruct the whole secret sharing system. Therefore, we introduce an efficient dynamic threshold scheme. In the new scheme, the shadowholders can reuse the secret shadows no matter that the shared secret is renewed or recovered. In addition, the new scheme provides a way by which the dealer can renew the shared secret or reconstruct the secret sharing system, efficiently. Therefore, this scheme is good for maintaining the important secrets.

GDL is the language whose membership problerm is polynomial-time Turing equivalent to the discrete logarithm problem for a general finite group G. This paper gives a characterization of GDL from the viewpoint of computational complexity theory. It is shown that GDL NP co-AM, assuming that G is in NP co-NP, and that the group law operation of G can be executed in polynomial time of the element size. Furthermore, as a natural probabilistic extension, the complexity of GDL is investigated under the assumption that the group law operation is executed in an expected polynomial time of the element size. In this case, it is shown that GDL MA co-AM if G MA co-MA. As a consequence, we show that GDL is not NP-complete unless the polynomial time hierarchy collapses to the second level.

This paper presents a zero-knowledge interactive protocol that demonstrates two factors a and b of a composite number n (=ab) are really known by the prover, without revealing the factors themselves. Here the factors a and b need not be primes. The security of the protocol is based on the difficulty of computing discrete logarithms modulo a large prime.

In 1990, Menezes, Okamoto and Vanstone proposed a method that reduces EDLP to DLP, which gave an impact on the security of cryptosystems based on EDLP. But this reducing is valid only when Weil pairing can be defined over the m-torsion group which includes the base point of EDLP. If an elliptic curve is ordinary, there exists EDLP to which we cannot apply the reducing. In this paper, we investigate the condition for which this reducing is invalid.